/*
 * @lc app=leetcode.cn id=47 lang=cpp
 *
 * [47] 全排列 II
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        multiset<int> numsLeft;
        for (auto& num : nums){
            numsLeft.insert(num);
        }

        vector<int> current{};

        // why std::set auto sort the std::vector<int> as key ???

        std::set<std::vector<int>> result;
        subPermute(current, numsLeft, result);

        vector<vector<int>> res;
        for (auto& candidate : result){
            res.emplace_back(candidate);
        }
        return res;
    }

private:
    void subPermute(vector<int>& current, multiset<int>& numsLeft, 
                    std::set<std::vector<int>>& result){
        int n = numsLeft.size();

        if (n == 1){
            int num = *(numsLeft.begin());

            current.push_back(num);
            result.emplace(current);
            current.pop_back();
            return;
        } else{
            for (int i=0;i<n;i++){
                auto numIter = numsLeft.begin();
                for(int ii=0;ii<i;ii++){numIter++;}
                int num = *numIter;

                current.push_back(num);

                numsLeft.erase(numIter);

                subPermute(current, numsLeft, result);

                numsLeft.insert(num);

                current.pop_back();
            }
        }
    }
};
// @lc code=end

